//
// Description: 5. 最长回文子串
// Created by Loading on 2021/9/16.
//

#include <bits/stdc++.h>

using namespace std;

/* 动态规划，时间复杂度：O(n^2) */
string longestPalindrome(string s) {
    int n = s.size();
    // dp 状态数组，dp[i][j] = true 表示 [i~j] 子串是回文串
    bool dp[n][n];
    memset(dp, false, sizeof dp);
    for (int i = 0; i < n; ++i) {
        dp[i][i] = true;
    }
    int start = 0;
    int maxLen = 1;
    /* 因为状态转移是从较短长度到较长长度，所以先枚举子串长度 */
    for (int len = 2; len <= n; ++len) {
        for (int i = 0; i < n; ++i) {
            int j = i + len - 1;
            if (j >= n) {
                break;
            }
            if (s[i] == s[j]) {
                if (j == i + 1) {
                    dp[i][j] = true;
                } else {
                    dp[i][j] = dp[i + 1][j - 1];
                }
                // 更新起始位置和最大长度
                if (dp[i][j] && len > maxLen) {
                    start = i;
                    maxLen = len;
                }
            }
        }
    }

    return s.substr(start, maxLen);
}

/* 中心扩展法，时间复杂度：O(n^2) */
string longestPalindrome_ExpandAroundCenter(string s) {
    // 以一个元素或两个元素为中心，向外扩展
    int n = s.size();
    int start = 0, len = 1;

    auto expand = [&](int i, int j) {
        // 按照中心，向外扩展，返回扩展后的起始与结束位置
        while (i >= 0 && j < n && s[i] == s[j]) {
            --i;
            ++j;
        }
        return pair<int, int>{i + 1, j - 1};
    };

    for (int i = 0; i < n; ++i) {
        // 一个元素为中心
        auto[s1, e1] = expand(i, i);
        // 两个元素为中心
        auto[s2, e2] = expand(i, i + 1);
        // 更新最大长度
        if (e1 - s1 + 1 > len) {
            start = s1;
            len = e1 - s1 + 1;
        }
        if (e2 - s2 + 1 > len) {
            start = s2;
            len = e2 - s2 + 1;
        }
    }

    return s.substr(start, len);
}

int main() {
    string s = "aaaa";
    string res = longestPalindrome(s);
    cout << res << endl;

    res = longestPalindrome_ExpandAroundCenter(s);
    cout << res << endl;

    return 0;
}